package labuladong;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Al02 {
    int fib(int n){
        if(n<1) return 0;
        int[] memo = new int[n+1];
        Arrays.fill(memo, 0);
        return helper(memo, n);
    }
    int helper(int[] memo, int n){
        if(n==1 || n==2) return 1;
        if(memo[n]!=0) return memo[n];
        memo[n] = helper(memo, n-1)+helper(memo, n-2);
        return memo[n];
    }

    int coinChange(int[] coins, int amount){
        if(amount<1) return 0;
        int[] dp = new int[amount+1];
        for (int i = 0; i <= amount; i++) {
            // 凑amount最多需要amount个钱币
            dp[i] = i;
        }
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if(i<coins[j]) continue;
                dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
            }
        }
        return dp[amount];
    }

    // 全排列
    List<List<Integer>> res = new ArrayList<>();
    List<List<Integer>> permute(int[] nums){
        if(nums == null || nums.length == 0) return res;
        List<Integer> stack = new ArrayList<>();
        backtrack(nums, stack);
        return res;
    }
    public void backtrack(int[] nums, List<Integer> stack){
        if(stack.size() == nums.length){
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(stack.contains(nums[i])) continue;
            stack.add(nums[i]);
            backtrack(nums, stack);
            stack.remove(stack.size()-1);
        }
    }

    // 二叉树最小深度
    int minDepth(TreeNode root){
        if(root == null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while(!que.isEmpty()){
            int sz = que.size();
            for (int i = 0; i < sz; i++) {
                TreeNode node = que.poll();
                if(node.left == null && node.right == null) return depth;
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
            }
        }
        return depth;
    }

    public String minWindows(String s, String t){
        if(s==null||s.length()==0||t==null||t.length()==0) return "";
        int[] need = new int[128];
        int[] window = new int[128];
        for(Character c : t.toCharArray()){
            need[c]++;
        }
        int l = 0, r = 0;
        int count = 0;
        String res = "";
        int minLength = s.length()+1;
        while(r < s.length()){
            char c = s.charAt(r);
            window[c]++;
            if(need[c]>0 && need[c] >= window[c]){
                count++;
            }
            while (count == t.length()) {
                char ch = s.charAt(l);
                if(need[ch]>0&&need[ch]>=window[ch]){
                    count--;
                }
                if(r-l+1 < minLength){
                    minLength = r-l+1;
                    res = s.substring(l, r+1);
                }
                window[ch]--;
                l++;
            }
        }
        return res;
    }
    
    // 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，
    // 第一个字符串的排列之一是第二个字符串的子串。
    public boolean checkInclusion(String s1, String s2){
        if(s1.length()>s2.length()) return false;
        int[] s1map = new int[26];
        int[] s2map = new int[26];
        for(int i=0; i< s1.length(); i++){
            s1map[s1.charAt(i)-'a']++;
            s2map[s2.charAt(i)-'a']++;
        }
        for (int i = 0; i < s2.length()-s1.length(); i++) {
            if(matches(s1map, s2map)) return true;
            s2map[s2.charAt(i+s1.length()-'a')]++;
            s2map[s2.charAt(i)-'a']--;
        }
        return false;
    }
    public boolean matches(int[] s1map, int[] s2map){
        for (int i = 0; i < 26; i++) {
            if(s1map[i]!=s2map[i]) return false;
        }
        return true;
    }

    // 无重复的最长字串
    public int lengestOfLongestSubstring(String s){
        if(s==null||s.length()==0) return 0;
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        int res = 0;
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if(map.containsKey(c[i])){
                left = Math.max(left, map.get(c[i])+1);
            }
            res = Math.max(res, i-left+1);
            map.put(c[i], i);
        }
        return res;
    }

    // 计算区间，对区间的end进行排序，把与最先结束区间相交的区间去掉，获得答案
    int intervalSchedule(int[][] intvs){
        if(intvs.length==0) return 0;
        Arrays.sort(intvs,new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[1]-b[1];
            }
        });
        int count = 1;
        int x_end = intvs[0][1];
        for(int[] interval : intvs){
            if(interval[0]>x_end){
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }

    // 信封问题
    int maxEnvelopes(int[][] envelopes){
        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0]==b[0]?a[1]-b[1]:a[0]-b[0];
            }
        });
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = envelopes[i][1];
        }
        int res = 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(height[j]<height[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    res = Math.max(res, dp[i]);
                }
            }
        }
        return res;
    }

    // 最长公共子序列
    int longestCommonSunsequence(String s1, String s2){
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1]+1;
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        
    }
    
}
